package com.algorithm.structure;

import lombok.*;

import java.util.*;

/**
 * 字典树结构查找最大公共字符串
 */
public class TrieTree {
    public static final  TrieNode root = new TrieNode();

    public static void main(String[] args) {
        String[] arr = {"abstract","abslout","cloud","current"};
        //TrieNode trieNode = addArray(arr);
        findCommonStr(arr[0],arr[1]);
    }

    private static void findCommonStr(String referer, String str) {
        TrieNode trieNode = addArray(new String[]{referer, str});
    }

    public static final TrieNode addArray(String[] strs){
        TrieNode trieNode = null;
        for (int i = 0; i < strs.length; i++) {
            trieNode = addString(strs[i]);
        }
        return trieNode;
    }

    public static final TrieNode addString(String str){
        TrieNode currentNode = root;
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            currentNode = currentNode.addChild(chars[i]);
        }
        return root;
    }

}
@NoArgsConstructor
@Data
class TrieNode {
    private char value;
    private TrieNode parent;
    private List<TrieNode> childSet = new LinkedList<>();

    public TrieNode(char value,TrieNode parent) {
        this.value = value ;
        this.parent = parent;
    }

    public TrieNode addChild(char childValue){
        TrieNode childNode;
        if (!this.childSet.isEmpty()){
            childNode = findChild(childValue);
            if (childNode != null) return childNode;
        }
        childNode = new TrieNode(childValue,this);
        childSet.add(childNode);
        return childNode;
    }

    public TrieNode findChild(char childValue) {
        for (TrieNode trieNode : childSet) {
            if (trieNode.getValue() == childValue){
                return trieNode;
            }
        }
        return null;
    }
}
